package com.zyk.leetcode;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/best-sightseeing-pair/
 *
 * @author zhangsan
 * @date 2021/3/31 10:03
 */
public class C1014 {

    // 暴力解 O(N平方)
    public static int maxScoreSightseeingPair(int[] values) {
        // 0 ~ N-1
        // 1 ~ N-1
        // 2 ~ N-1
        // N-2 ~ N-1
        int max = 0;
        for (int i = 0; i < values.length - 1; i++) {
            for (int j = i + 1; j < values.length; j++) {
                max = Math.max(max, (values[i] + values[j] + i - j));
            }
        }
        return max;
    }

    // 更复杂了.毫无意义
    public static int maxScoreSightseeingPair2(int[] values) {
        int N = values.length;
        int[][] dp = new int[N-1][N];
        for (int r = 0; r < N-1; r++) {
            dp[r][r] = values[r];
            int i = 1;
            for (int c = r+1; c < N; c++) {
                dp[r][c] = values[c]-(i++);
            }
        }

        int max = 0;
        for (int j = 0; j < dp.length; j++) {
            int max1 = Math.max(dp[j][j], dp[j][j+1]), max2 = Math.min(dp[j][j], dp[j][j+1]);
            for (int i = j+2; i < dp[j].length; i++) {
                if(dp[j][i] > max2) {
                    max2 = dp[j][i];
                    if(max2 > max1) {
                        max1 = max1^max2;
                        max2 = max1^max2;
                        max1 = max1^max2;
                    }
                }
            }
            max = Math.max(max, (max1+max2));
        }

        return max;
    }


    public static int maxScoreSightseeingPair3(int[] values) {
        int ans = 0, mx = values[0] + 0;
        for (int j = 1; j < values.length; ++j) {
            ans = Math.max(ans, mx + values[j] - j);
            // 边遍历边维护
            mx = Math.max(mx, values[j] + j);
        }
        return ans;
    }

    // for test
    public static int[] generateArray(int maxLen, int maxVal) {
        maxLen = (int) (Math.random()*maxLen)+1;
        int[] res = new int[maxLen];
        for (int i = 0; i < maxLen; i++) {
//            res[i] = (int) (Math.random()*maxVal +1 - Math.random()*maxVal);
            res[i] = (int) (Math.random()*maxVal +1);
        }
        return res;
    }

    // for test
    public static void main(String[] args) {
        /*int[] values = {5,7,4,10,4};
        int r1 = maxScoreSightseeingPair(values);
        int r2 = maxScoreSightseeingPair2(values);
        System.out.println(r1);
        System.out.println(r2);*/

        int maxLen = 2000;
        int maxVal = 20;
        int times = 2000;
        for (int i = 0; i < times; i++) {
            int[] values = generateArray(maxLen, maxVal);
            int r1 = maxScoreSightseeingPair(values);
            int r2 = maxScoreSightseeingPair2(values);
            int r3 = maxScoreSightseeingPair3(values);
            if(r1 != r2) {
                System.out.println("OOPS");
                System.out.println(Arrays.toString(values));
                System.out.println(r1);
                System.out.println(r2);
                System.out.println(r3);
                break;
            }
        }

    }

}
